package leetcode_800;

/**
 *@author 周杨
 *CouplesHoldingHands_765
 *describe:
 *2018年10月19日 上午9:52:02
 */
public class CouplesHoldingHands_765_ {
	/**
	 * describe:贪心算法 每次就通过往后遍历找到这个cp AC 13% 当前面的排好序后  后面的自然是有序的
	 * 2018年10月19日 上午9:54:51
	 */
	public int minSwapsCouples(int[] row) {
		int res = 0, n = row.length;
        for (int i = 0; i < n; i += 2) {
            if (row[i + 1] == (row[i] ^ 1)) continue;//异或立即将最后一位处理
            ++res;
            for (int j = i + 1; j < n; ++j) {//从下一位开始找 因为前面的已经到位了
                if (row[j] == (row[i] ^ 1)) {//交换两者
                    row[j] = row[i + 1];
                    row[i + 1] = row[i] ^ 1;
                    break;
                }
            }
        }
        return res;
    }
	
	/**
	 * describe:用并查集 AC 100%
	 * 2018年10月19日 上午10:08:54
	 */
	public int minSwapsCouples1(int[] row) {
		int res=row.length/2;
		int []root=new int[row.length];
		for(int i=1;i<row.length;++i) root[i]=i;
		for(int i=0;i<row.length;i+=2) {//一次处理两个数
			int x=find(root,row[i]/2);
			int y=find(root,row[i+1]/2);
			if(x!=y) {
				root[x]=y;
				--res;
			}
		}
		return row.length/2-res;//最终这个交换的计算我不是很懂
	}
	
	public int find(int []root,int target) {
		return target==root[target]?target:find(root,root[target]);
	}
}
